package com.lw.leetcode.arr.b;

import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * <p>
 * arr
 * 1072. 按列翻转得到最大值等行数
 *
 * @author liw
 * @version 1.0
 * @date 2021/8/9 13:43
 */
public class MaxEqualRowsAfterFlips {
    public static void main(String[] args) {
        MaxEqualRowsAfterFlips test = new MaxEqualRowsAfterFlips();
        // 2
        int[][] arr = {
                {1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1},
                {1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0},
                {1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1},
                {1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0},
                {1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1}};
        int i = test.maxEqualRowsAfterFlips(arr);
        System.out.println(i);
    }

    private int max = 0;
    private int n;

    public int maxEqualRowsAfterFlips(int[][] matrix) {
        int m = matrix.length;
        n = matrix[0].length;
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            list.add(i);
        }
        find(matrix, 1, list);
        return max;
    }

    private void find(int[][] arr, int index, List<Integer> list) {
        if (list.isEmpty()) {
            return;
        }
        if (index == n) {
            max = Math.max(list.size(), max);
            return;
        }
        List<Integer> a = new ArrayList<>();
        List<Integer> b = new ArrayList<>();
        for (int value : list) {
            if (arr[value][index] == arr[value][index - 1]) {
                a.add(value);
            } else {
                b.add(value);
            }
        }
        find(arr, index + 1, a);
        find(arr, index + 1, b);
    }
}
